<?php
/**
 * @title 面试题 17.13. 恢复空格 - 递归+剪枝
 * @author start2004
 */

class Solution {

    /**
     * @param String[] $dictionary
     * @param String $sentence
     * @return Integer
     */
    function respace($dictionary, $sentence) {
        /**
         * @since 2020-10-13 字典最大长度, 最小长度
         */
        $this->lens = [];

        /**
         * @since 2020-10-13 字典哈希
         */
        $this->hashs = [];
        foreach ($dictionary as $word){
            $len = strlen($word);
            $this->lens[$len] = $len;
            $this->hashs[$word] = 1;
        }

        /**
         * @since 2020-10-13 长度升序
         */
        sort($this->lens);

        /**
         * @since 2020-10-13 缓存
         */
        $this->dps = [];

        /**
         * @since 2020-10-13 未识别的字符最少
         */
        $min = self::find($sentence);

        /**
         * @return
         */
        return $min;
    }

    /**
     * @title 最少未知字符数
     * @author start2004
     * @since 2020-10-13 Created
     *
     * @param string $sentence
     * @return int|mixed
     */
    public function find($sentence = ''){
        if(isset($this->dps[$sentence])){
            return $this->dps[$sentence];
        } else {}

        /**
         * @since 2020-10-13 未知字符
         */
        $slen = $minUnknowWordLen = strlen($sentence);
        if($slen == 0){
        } elseif(isset($this->hashs[$sentence])) {
            /**
             * @since 2020-10-13 完整匹配, 不需要往下匹配
             */
            $minUnknowWordLen = 0;
        } else {
            /**
             * @since 2020-10-13 字符长度
             */
            foreach ($this->lens as $len){
                if($len > $slen){
                    break;
                } else {}

                $word = substr($sentence, 0, $len);
                if(isset($this->hashs[$word])){
                    $minUnknowWordLen = min($minUnknowWordLen, self::find(substr($sentence, $len)));
                } else {}
            }

            /**
             * @since 2020-10-13 丢弃一个字符
             * @since 2020-10-13 如果第1个字符存在, 或者迭代出未知字符是1个, 舍弃1个字符都不会得到更少的未知字符长度
             */
            if(!isset($this->hashs[$sentence[0]]) AND $minUnknowWordLen>=2){
                $minUnknowWordLen = min($minUnknowWordLen, 1+self::find(substr($sentence, 1)));
            } else {}
        }

        /**
         * @return
         */
        $this->dps[$sentence] = $minUnknowWordLen;
        return $minUnknowWordLen;
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.23_10.php
 */
$datas = [
    [["frrrbbrrbfrfqqbbbrb","qr","b","rf","qqbbbbfrqbrrqrffbrqqqbqqfqfrr","r","ffqq","bffbqfqqbrrrf","fq","qfr","fr","rqrrbfbfq","r","f","qbqbrbrbqfqbbbfbbbfbq","bqqbbbqrbbrf","f"], "bqqffbqbbfqrfrrrbbrrbfrfqqbbbrbfqfffffrfqfqfffffrrfqfrrqbqfrbfrqqrfrbrbbqbqbqqfqrfbfrfr"], // 9
    [["patk","mk","bgmuaukzpbp","tpakjawagaakakmpkkikjpbmppiiazkkdko","apoggddaakoadudmw","mugaxmgwkbptxmbmt","tijagbkixiwzdddbbjjgpk","goaotk","kk","xambkwpozgouaaamzgtpkojgdbxuwkjz","gmwo","bkbpdptkjxjgatdkukxmxkabkjmiuotiikb","ad","babtgmz","kujuak","ikimadpozaxozoaikttzamjakk","jjumibouto"], "bgmuaukzpbpkujuakpatk"], //0

    [["looked","just","like","her","brother"], "jesslookedjustliketimherbrother"], // 7

    [["right", "righting"], "rightinglobal",], // 5, 优先最短匹配会出问题

    [["right", "righting", "global"], "rightinglobal"], // 2, 优先最长匹配会出问题

    [["right", "righting", "tinglobal"], "rightinglobal"], // 4, 优先最长和最短匹配混用也会出问题

    [["right", "global","tinglobal"], "rightinglobal"], // 2

    [["right", "righting", "global", "ightin"], "rightinglobal"], // 1

    [["right", "righting", "righ", "tin", "ri", "global"], "rightinglobal"], // 0

    [["right", "righting", "ri", "h", "global"], "rightinglobal"], // 2

];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    // var_dump($data);

    $obj = new Solution();
    $result = $obj->respace($data[0], $data[1]);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
